loop detection
Given $ f(x), I want to find $ f^n(x) fast
The domain and value range of f are common finite sets
The starting point x is a single
If the size of the definition region is D and the maximum value of n is N, then the pre-processing O(D) can be made into the main process O(1)
pretreatment
Prepare two arrays A and B
$ A: f^i(x) \to i
$ B: i \to f^i(x)
Fill this array by incrementing i
If Ai is not the initial value, it is a loop
Can be determined by constant order.
Worst case scenario, a loop is found by D
main processing
i, Ai to the loop and the length of the path and the length of the loop until it enters the loop.
loop_start = Ai
loop_length = i - Ai
Constant Order $ f^n(x) = (n - A_i) \% (i - A_i)
---
This page is auto-translated from /nishio/ループ検出. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.